package de.dopichaj.labrador.search.hit;

import java.io.PrintWriter;
import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;

import org.apache.commons.lang.StringEscapeUtils;

/**
 * A tree structure for merging hits.
 * 
 * Initially, all hits are in the results; users of this class
 * may then delete them.
 */
public class HitHierarchyTree {

    private final Hit root;
    
    private static final class TreeNode {
        /** A map from the XPath part to the corresponding child */
        private Map<String, TreeNode> children = new HashMap<String, TreeNode>();
        private Hit hit;
        private boolean isResult = true;
        
        public Hit getHit() {
            return hit;
        }
        public void setHit(Hit hit) {
            this.hit = hit;
        }
        
        public TreeNode getChild(String xPathPart) {
            return children.get(xPathPart);
        }
        
        public TreeNode getOrAddChild(String xPathPart) {
            if (children.containsKey(xPathPart)) {
                return children.get(xPathPart);
            } else {
                return addChild(xPathPart);
            }
        }
        
        public TreeNode addChild(String xPathPart) {
            final TreeNode child = new TreeNode();
            
            assert !children.containsKey(xPathPart);
            children.put(xPathPart, child);
            return child;
        }
        
        public Collection<TreeNode> getChildren() {
            return children.values();
        }
    }
    
    private final TreeNode rootNode = new TreeNode();
    private final Map<Hit, TreeNode> nodeMap = new HashMap<Hit, TreeNode>();
    
    /**
     * Generates a hashtable from the hitVector that contains the
     * path as key and a tree as value that is ordered according to
     * the xpath.
     * 
     * @param hitList The list of hits (must be from the same document).
     */    
    public HitHierarchyTree(Collection<Hit> hitList) {
        
        // for each hit
        for (final Hit hit : hitList) {
            
            // for each XPath part
            TreeNode node = rootNode;
            for (final String xPathPart : hit.getXPathParts()) {
                
                // find (or create) the corresponding de.dopichaj.labrador.index level
                node = node.getOrAddChild(xPathPart);
            }
            
            // add the hit at this de.dopichaj.labrador.index point
            node.setHit(hit);
            nodeMap.put(hit, node);
        }

        // find the root node;
        if (hitList.size() > 0) {
            Hit possibleRoot = null;
            for (final Hit hit : hitList) {
                if (hit.getDepth() == 0) {
                    possibleRoot = hit;
                    break;
                }
            }
            root = possibleRoot;
        } else {
            root = null;
        }

    }
    
    /**
     * Get the root node of the tree.
     */
    public Hit getRoot() {
        return root;
    }
    
    /**
     * Get the parent of a node.
     * @param hit A Hit
     * @return The parent of the hitNode, or null if the given
     * Hit is the root node. 
     */
    public Hit getParent(Hit hit) {

        final String[] xPathParts = hit.getXPathParts();
        TreeNode node = rootNode;
        for (int i = 0; i < xPathParts.length - 1; i++) {
            node = node.getChild(xPathParts[i]);
        }
        Hit parentHit = node.getHit();
        if (parentHit == null && hit.getDepth() != 0) {
            parentHit = new MemoryHit(hit.getFile(), hit.getEnclosingXPath());
            node.setHit(parentHit);
        }
        
        return parentHit;
    }
    
    private final Map<Hit, SortedSet<Hit>> childCache = new HashMap<Hit, SortedSet<Hit>>();
    /**
     * Get the children of a Hit in this tree.
     * @param hit A Hit
     * @return The children of the hit, sorted by position
     */
    public SortedSet<Hit> getChildren(Hit hit) {

        if (childCache.containsKey(hit)) {
            return childCache.get(hit);
        } else {
            final TreeNode node = getTreeNode(hit);
            final SortedSet<Hit> children = new TreeSet<Hit>(PosComparator.INSTANCE);
            for (final TreeNode childNode : node.getChildren()) {
                
                if (childNode.getHit() != null) {
                    children.add(childNode.getHit());
                }
            }
            childCache.put(hit, children);
            return children;
        }
    }

    private static final class TreeNodeToHitIterator implements Iterator<Hit> {
        private final Iterator<TreeNode> baseIterator;
        private Hit nextHit;
        
        public TreeNodeToHitIterator(Iterator<TreeNode> baseIterator) {
            this.baseIterator = baseIterator;
            getNextHit();
        }

        private void getNextHit() {
            nextHit = null;
            while (nextHit == null && baseIterator.hasNext()) {
                nextHit = baseIterator.next().getHit();
            }
        }

        public boolean hasNext() {
            return nextHit != null;
        }

        public Hit next() {
            final Hit hit = nextHit;
            getNextHit();
            assert hit != null;
            return hit;
        }

        public void remove() {
            baseIterator.remove();
        }
        
        
    }
    private static final class TreeNodeToHitWrapper extends AbstractCollection<Hit> {

        private final Collection<TreeNode> base;
        
        public TreeNodeToHitWrapper(final Collection<TreeNode> base) {
            this.base = base;
        }
        
        @Override
        public Iterator<Hit> iterator() {
            return new TreeNodeToHitIterator(base.iterator());
        }

        @Override
        public int size() {
            return base.size();
        }

    }
    
    public Collection<Hit> getUnsortedChildren(Hit hit) {
        return new TreeNodeToHitWrapper(getTreeNode(hit).getChildren());
    }

    /**
     * Get the TreeNode for the given Hit.
     */
    private TreeNode getTreeNode(Hit hit) {
        
        return nodeMap.get(hit);
    }
    
    private void addDescendants(TreeNode node, Collection<Hit> descendants,
        boolean onlyResults) {
        
        for (final TreeNode child : node.getChildren()) {
            if (child.getHit() != null && (!onlyResults || child.isResult)) {
                descendants.add(child.getHit());
            }
            addDescendants(child, descendants, onlyResults);
        }
    }
    
    public Collection<Hit> getAllHits() {
        final Collection<Hit> result = new ArrayList<Hit>();
        addDescendants(rootNode, result, false);
        return result;
    }
    
    /**
     * Get all the hits that are marked "in result set".
     */
    public Collection<Hit> generateHitList() {
        final Collection<Hit> result = new ArrayList<Hit>();
        addDescendants(rootNode, result, true);
        return result;
    }

    /**
     * Get the siblings of a given node.
     * @return The siblings of the node, sorted by position.
     */
    public SortedSet<Hit> getSiblings(Hit node) {
        Hit parent = getParent(node);
        if (parent != null) {
            return getChildren(parent);
        } else {
            SortedSet<Hit> siblings = new TreeSet<Hit>();
            siblings.add(node);
            return siblings;
        }
    }

    public void removeFromResults(Hit hit) {
        final TreeNode node = getTreeNode(hit);
        assert node != null : "No TreeNode available for " + hit;
        node.isResult = false;
    }
    
    public boolean isInResults(Hit hit) {
        return getTreeNode(hit).isResult;
    }
    
    private void writeRecursive(PrintWriter writer, String indent, Hit hit) {
    
        // print the hit
        String xPath = hit.getXPath().replaceFirst("^.*/", "");
        writer.println(indent + "<hit " +
                "xpath='" + StringEscapeUtils.escapeXml(xPath) + "' " +
                "length='" + hit.getContentLength() + "' " +
                "pos='" + hit.getPosition() + "' " +
                "score='" + hit.getScore() + "' " +
                ">");

        // print the children
        String newIndent = indent + "  ";
        for (Hit child : getChildren(hit)) {
            writeRecursive(writer, newIndent, child);
        }
        
        writer.println(indent + "</hit>");
    }
    
    /**
     * Write the tree to a stream in XML format. No XML header is written and the
     * writer is not closed, so you can write several trees to the same writer.
     */
    public void write(PrintWriter writer) {
        Hit root = getRoot();
        writer.println("<resulttree document='" + StringEscapeUtils.escapeXml(root.getFile().toString()) + "'>");
        writeRecursive(writer, "  ", root);
        writer.println("</resulttree>");
    }
    
    @Override
    public String toString() {
        return "[Tree for " + root.getFile() + "]";
    }
}
/*
Copyright (c) 2005 Benedikt Eger
Copyright (c) 2005-2007 Philipp Dopichaj

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/